#include "soc_io.h"

/*-------------------------------------------------------------------------------------------*/
/*--------------------------------- 第1部分代码 ---------------------------------------*/
/*-------------------------------------------------------------------------------------------*/
#define STR_LEN 6  // "babad" + 末尾的 '\0'

/* 待测字符串 */
char s[STR_LEN] = "babad";

/* 事先计算好的最长回文子串长度 (对于 "babad" 而言是 3，如 "bab" 或 "aba") */
int ans_lps = 3;

/*-------------------------------------------------------------------------------------------*/
/*--------------------------------- 第2部分代码 ---------------------------------------*/
/*-------------------------------------------------------------------------------------------*/
/* 手动实现一个获取字符串长度的函数（不使用 <string.h>） */
int str_length(const char *str) {
    int len = 0;
    while(str[len] != '\0') {
        len++;
    }
    return len;
}

/*
 * 马拉车算法函数：返回字符串 s 的最长回文子串长度
 * 不使用任何 C 标准库函数来处理字符串。
 */
int manacher_lps_length(const char *s) {
    /* 先求原始字符串长度 */
    int n = str_length(s);
    if(n == 0) return 0;

    /* 
       为了处理奇、偶回文，构造带分隔符的字符串。
       这里示例使用形式：^#s[0]#s[1]#...#s[n-1]#$ 
       注意要留下足够的空间存放 '^', '#', '$', '\0' 等。
       
       长度计算：给每个字符前加 '#'，再在开头放 '^'，结尾放 '#', '$'，例如：
         原字符串长度：n
         加 '#' 的中间部分长度：2*n + 1
         再加开头 '^' (1 个字符) 和 结尾 '$' (1 个字符) 以及中间结尾的 '#' (1 个字符)
         总共长度 ~ 2n + 4
       为保险起见，开数组时可适当多留一点空间。
    */
    int temp_len = 2 * n + 4;
    char temp[2 * STR_LEN + 10];
    int p[2 * STR_LEN + 10];  // p[i] 表示以 i 为中心的回文半径

    /* 构造带分隔符的字符串 */
    int idx = 0;
    temp[idx++] = '^';
    temp[idx++] = '#';
    int i;
    for(i = 0; i < n; i++) {
        temp[idx++] = s[i];
        temp[idx++] = '#';
    }
    temp[idx++] = '$';
    temp[idx] = '\0';  // 字符串结束符

    /* 马拉车算法核心部分 */
    int center = 0, right = 0, max_len = 0;
    for(i = 1; i < temp_len - 1; i++) {
        /* 当 i >= (真正构造完的) temp 的有效长度时，就不用再做处理了 */
        if(temp[i] == '\0') break; 

        /* mirror 是 i 关于 center 的对称位置 */
        int mirror = 2 * center - i;

        /* 根据对称中心获取一个初始 p[i] */
        if(i < right) {
            /* 如果 p[mirror] 未超出以 center 为中心的回文右边界，则可以直接继承 */
            int distance_to_right = right - i;
            if(p[mirror] < distance_to_right) {
                p[i] = p[mirror];
            } else {
                p[i] = distance_to_right;
            }
        } else {
            p[i] = 0;
        }

        /* 试着向左右两边扩展，比较 temp[i + 1 + p[i]] 和 temp[i - 1 - p[i]] */
        while(
            (i + 1 + p[i]) < temp_len &&
            (i - 1 - p[i]) >= 0 &&
            temp[i + 1 + p[i]] == temp[i - 1 - p[i]] &&
            temp[i + 1 + p[i]] != '\0' &&
            temp[i - 1 - p[i]] != '\0'
        ) {
            p[i]++;
        }

        /* 如果扩展后超出了以前的 right，则更新 center 和 right */
        if(i + p[i] > right) {
            center = i;
            right = i + p[i];
        }

        /* 记录最大回文半径 */
        if(p[i] > max_len) {
            max_len = p[i];
        }
    }

    /* max_len 就是原字符串中最长回文子串的长度 */
    return max_len;
}

int main() {
    init();      // 假设为测试环境初始化函数
    int flag = 1; // 测试结果标志

    int lps = manacher_lps_length(s);
    if(lps != ans_lps) {
        flag = 0;
    }

    print_result(flag); // 输出测试结果

    while(1);
    return 0;
}